package examination_practice01;

import java.util.Arrays;

class Item{
    public int weight;
    public int value;
    public Item(int weight,int value){
        this.weight=weight;
        this.value=value;
    }
}
public class Knapsack {
    //贪心算法求解0-1背包问题
    public static int getMaxValue(Item[] items,int capacity){
        //按照单位价值比从大到小排序
        Arrays.sort(items,(item1,item2)->{
            double ratio1=(double) item1.value/item1.weight;
            double ratio2=(double)item2.value/item2.weight;
            if (ratio1<ratio2){
                return 1;
            }else if (ratio1>ratio2){
                return -1;
            }else{
                return 0;
            }
        });
        int totalValue=0;//背包中的总价值
        int currentCapacity=capacity;

        for (Item item:items){
            if (item.weight<=currentCapacity){
                totalValue+=item.value;
                currentCapacity-=item.weight;
            }
        }
        return totalValue;
    }
    public static void main(String[] args){
        Item[] items={new Item(10,60),//6
        new Item(5,20),//4
        new Item(8,24),//3
        new Item(7,35),//5
        new Item(20,60)};//3
        int capacity=25;
        int maxValue=getMaxValue(items,capacity);
        System.out.println("背包的最大价值为："+maxValue);
    }
}
